1. Field of the Invention
The present invention relates to digital printing devices, and, in particular, to methods and apparatus for generating dither arrays for use in halftoning operations that convert a grayscale input to a binary output suitable for printing.
2. Description of the Related Art
Most computer-driven printing devices which generate hard copy, such as laser, dot-matrix and ink-jet printers, print in a binary fashion--the output medium is divided into an array of picture elements or "pixels" and the devices can either print a small colored dot at each pixel location or leave the pixel location blank. In the case of monochrome printers, all of the dots are printed with a single color whereas with color printers a dot color is chosen from a small set of colors. In any case, the dot itself has a uniform color so that the resulting output consists of an array of colored and blank pixels.
Pictorial images such as those produced by photographic techniques or by computerized imaging systems, by contrast, are continuous in tonality. If such an image is divided into pixels, each pixel exhibits a "grayscale" color whose tonal value falls within a range of tonal values. In order to reproduce such "continuous-tone" images by means of electronic printing, the images must therefore be converted into a form which is suited to the characteristics of the printing device, generally a binary format. This conversion process, which may take many forms, is generically referred to as "halftoning." Although a halftone image actually consists solely of a spatial pattern of binary pixels (colored or blank dots), the human visual system integrates this pattern to create an illusion of a continuous-tone image.
During the printing process, the image to be printed is divided into a series of pixels and the value of the image in each pixel is quantized to produce a multi-bit digital word which represents the tonal value of the pixel. The image is thus converted to a stream of digital words which are provided to the printing device. In order to convert the format of each word into a format suitable for reproduction on the digital device, halftoning is performed on the digital word stream during a process called preprocessing. Numerous halftoning techniques have been developed and refined over the years. In their simplest form, such techniques compare the value of each digital word with a threshold level, and generate a binary output pixel value depending on the relative values.
For example, a digital scanner processing a continuous-tone image might generate a stream of multi-bit words representing the detected light intensities. Commonly, the numerical value of these words ranges from 0 to 255, corresponding to a 256-level gray scale or an eight-bit word. If such a digital word stream is to be reproduced on a binary printing device, the halftoning process compares the scanner output words with a either a single threshold value or an array of threshold values to produce the required binary output pixel stream. In such a system, each 8-bit scanner word has effectively been compressed into a single-bit output word.
Naturally, such compression produces a significant loss of visual information and, in turn, creates distortions in the reproduced image that are not present in the original image. Additional techniques have therefore been developed to reduce the visual distortions created by the halftoning process. One approach, known as "error diffusion", attempts to "diffuse" the "quantization error" (i.e., the difference between the input value represented by a multi-bit word and the output value represented by a single bit or two multi-bit words) proportionally among neighboring pixels. During one embodiment of the error diffusion process, the input pixels represented by the input words are processed in "raster" order (line-by-line with each line being processed from left to right before the next lower line is processed). Each pixel is processed by comparing its value to a predetermined threshold value and the resulting quantization error, multiplied by a proportional coefficient, is added to the neighboring, but unprocessed, pixel values (in one illustrative embodiment, the pixel to the right of the one being processed and the three neighboring pixels in the following pixel line). The proportional coefficients are selected to add to 100%. The next pixel, comprising its original value plus the portion of the quantization error produced by the processing of the previous pixel, is then processed in the same manner. In this manner, the quantization error is spread or diffused over several pixels.
In general, error diffusion produces an excellent image reproduction, but also creates well-known artifacts called "worms" and "snowplowing" which degrade image quality. Various attempts have been made to vary the processing order (from the raster scan order of the illustrative embodiment) in order to reduce the artifact patterns. These attempts have been only partially successful as the artifact patterns were not totally removed but were changed in appearance or orientation in a manner that was more pleasing to the eye.
In addition, another problem inherent in the error diffusion method is the large number of computations which must be made to process an image. Since several computations, including multiplications, must be performed for each pixel which is processed, a typical high-resolution image may require many millions of computations to generate the final output values. In addition, it is necessary to store at least one line of error values which are to be applied to the following line of image values. This large number of computations and the required storage combine to increase the processing time for each image which processing time increase directly results in decreased printing device throughput.
Accordingly, additional halftoning techniques have been developed to reduce the computations involved to process an image. One such conventional halftone technique is called "ordered dithering". In accordance with conventional ordered dithering techniques, an array of predetermined, generally different, threshold values (called a dither array) with the same spacing as the image pixels is conceptually overlaid onto the image pixel array. If the dither array is smaller than the image array, then the dither array is repeated side-by-side or "tiled" over the image array to produce a repetitive pattern. Each pixel thus conceptually has two values associated with it, the actual pixel tonal value and the threshold value of the overlaid dither array. Equivalently, the values in the dither array can be added to the image value of each pixel prior to a comparison with a fixed threshold.
Each pixel is then processed by comparing its tonal value to the associated dither array value (or the augmented pixel value is compared to a fixed threshold) and the output pixel value is generated based on the comparison. Since the processing of each pixel involves only a simple comparison and is independent of neighboring pixel values, the computation time required to process an entire image is greatly reduced from the error diffusion processing time.
However, the quality of the resulting processed image is entirely dependent on the threshold values chosen for the dither array. In general, there are two types of dither arrays in common use. The first is called a "cluster-dot" dithering array and, in such an array, the threshold values are arranged in small clusters of similar-valued threshold numbers. The clusters of values in such arrays mimic "dots" of various sizes and thus produce a processed image with the same characteristics as produced by the traditional halftone screens used for years in photoengraving processes.
The second type of dither array is called a "dispersed-dot" dither array in which the different threshold values are spread evenly over the entire array. For image reproduction devices which can display clearly a single isolated pixel, the dispersed dot dither array usually produces better processed image quality than the cluster-dot dither array because high frequency fidelity is better and dispersed-dot arrays create a better illusion of a constant gray region than do cluster-dot arrays of the same resolution and period.
With both types of arrays, a tradeoff generally exists between the number of discrete gray levels that can be represented (which increases as the number of dither array elements increases) and the appearance of annoying low-frequency geometrical patterns in areas of uniform gray (which also appear as the number of dither array elements increases). Increasing the size of the dither array also tends to decrease image resolution as low frequency values disappear. One way to reduce these patterns and to retain resolution is to make the size of the dither array very large and utilize homogenous patterns of threshold values where successive threshold values "turn on" pixels in a homogenous random pattern. However, as the array size increases, assigning threshold values to the array cells to produce such a homogenous pattern becomes a non-trivial matter. Accordingly, various prior art schemes have been developed to derive the random threshold sequences and assign them to the array cells.
One common technique used to create a homogenous ordered dither array is called "recursive tesselation". The goal of recursive tessellation is to assign threshold values to each of the dither array cells in such a way that, as each successive cell is numbered or "turned on", the two-dimensional array of "on" cells is as homogeneously arranged as possible. Thus, when the dither array is used as a threshold array in a halftoning process, the corresponding arrangement of output binary dots will be disbursed as homogeneously as possible for each gray level to be simulated.
The algorithm used in recursive tessellation for generating the threshold array is based on the fact that if a regular geometric shape or "tile" is used cover or tesselate the two-dimensional dither array, the center point of the shape and its vertices can serve as center points for a retesselation of the array with new tiles of the same geometric shape but sized one cell smaller. In turn, the center points and vertices of these new tiles can act as center points for another retesselation with tiles that are again one cell smaller.
In accordance with the recursive tessellation algorithm, all of the tile vertices at each stage of this recursive tessellation are assigned threshold numbers before the next tessellation takes place. The algorithm provides a mechanism for locating a family of points that are exactly in the center of voids which occur between the vertex points of the tiles. Essentially, new points are added in the largest "voids" or areas where there is an absence of "on" pixels. The recursive tesselation method and the resulting threshold arrays are described in detail in "Digital Halftoning" by Robert Ulichney, printed by the MIT Press, Cambridge, Massachusetts and London, England, 1990, pages 128-171. While the recursive tessellation method can produce large dither arrays, these arrays suffer from a strong periodic structure that imparts an unnatural appearance to the resulting images when the arrays are used in a conventional halftoning operation.
Consequently, other prior art methods have been developed to generate dither arrays and one of these prior art methods is called a "blue noise mask". In general, "blue noise" is the high-frequency portion of a white noise spectrum. The power spectrum of blue noise has a low-frequency cutoff and is flat out to some fine high frequency limit. In general, the dot patterns produced by a blue noise mask are aperiodic and radially symmetric and these patterns produce an aperiodic, uncorrelated dither array structure without low frequency graininess. The choice of a blue noise mask arose from studies of the frequencies present in dot patterns produced by the error diffusion process described previously. When these dot patterns are converted into to a power spectrum of power versus frequency, it can be seen that the power spectrum has a low frequency cutoff point which occurs in the blue light frequency range, hence the name "blue noise".
The shape of the power spectrum can be used to construct dither arrays by examining dot patterns which produce blue noise power spectra and creating dither arrays from these dot patterns. The resulting arrays produce a high-quality output, however, the conversions between the frequency and spatial domains necessary to derive the arrays produces a complicated algorithm for generating the dither arrays. Blue noise masks are described in more detail in "Digital Halftoning Using A Blue Noise Mask", T. Mitsa and K. Parker, Proceedings SPIE, Image Processing Algorithms And Techniques II, v.1452, pps. 47-56, Feb. 21st-Mar. 1, 1991.
Another prior art technique for generating a large, homogeneous dither array is called the "void-and-cluster method". Again, the goal of this latter method is to produce a homogeneous distribution of 1's and 0's by starting with an initial pattern and removing pixels from the center of the tightest "clusters" and inserting them into the largest "voids". The void-and-cluster method is described in detail in "The Void-and-Cluster Method For Dither Array Generation", Robert Ulichney, IS&T/SPIE Symposium on Electronic Imaging Science and Technology, San Jose, Calif., Feb. 3, 1993 and "Filter Design For Void-and-Cluster Dither Arrays", Robert Ulichney, Society for Information Display International Symposium, San Jose, Calif., Jun. 14-16, 1994, the contents of which are hereby incorporated by reference.
In particular, in accordance with the aforementioned articles, the initial pattern used to generate the dither arrays is called a "Prototype Binary Pattern" and the terms "cluster" and "void" are defined in terms of "minority pixels" and "majority pixels". When less than half of the pixels in the Prototype Binary Pattern are of a particular type (either "1's" or "0's") they are denoted as minority pixels and the other type of pixel is denoted as a majority pixel. Using these definitions of minority and majority pixel, the terms "cluster" and "void" refer to the arrangement of minority pixels on a background of majority pixels. In particular, a "void" is a large space between minority pixels and a "cluster" is a tight grouping of minority pixels. During the processing of the Prototype Binary Pattern, minority pixels are always added to the center of the largest voids and are removed (or replaced with a majority pixel) from the center of the tightest cluster in order to homogenize the pattern.
The void-and-cluster method consists of three distinct steps:
(A) generating the Prototype Binary Pattern; PA1 (B) "homogenizing" the Prototype Binary Pattern by removing pixels from the clusters and assigning them to the voids to generate a homogenized Initial Binary Pattern; and PA1 (C) assigning dither array threshold numbers to the resulting homogenized Initial Binary Pattern.
More specifically, the Prototype Binary Pattern is generated by using any convenient technique that generates an input pattern where not more than half the pixels are "1's" and the rest are "0's". For example, a white noise pattern will serve as the Prototype Binary Pattern.
The next step in the method is to find the "voids" and the "clusters" so that pixels can be moved between the voids and clusters. Voids and clusters are located by means of a filter which examines the neighboring pixels bordering each pixel being processed. In particular, a void-finding filter considers the neighborhood pixels around every majority pixel in the Prototype Binary Pattern and a cluster-finding filter considers the neighborhood pixels around every minority pixel. In the aforementioned articles, a two-dimensional Gaussian filter represented by the function: ##EQU1## is used in order to find voids and clusters. During this processing, the values in the array are repeatedly processed and a single pixel may be moved several times from cluster to void. This processing is performed iteratively until the voids stop getting smaller and the clusters stop getting looser. Processing is deemed complete when removing the "1" from the tightest cluster in the pattern creates the largest void. The resulting homogenized pattern is called the Initial Binary Pattern.
In accordance with the third step of the method, the dither array is built from the Initial Binary Pattern by assigning threshold values to the dither array using the Initial Binary Pattern. In performing this step, the Initial Binary Pattern and the dither array are manipulated in parallel in three phases in accordance with a predetermined algorithm. Threshold values are assigned to the dither array cells based on the "rank" value of the "1's" in the Initial Binary Pattern. In particular in Phase I, one minority pixel or "1" is removed at a time from the Initial Binary Pattern while, in parallel, the rank or the number of minority pixels remaining in the Initial Binary Pattern is entered into the dither array in the location corresponding to the location of the removed "1". In each case, the minority pixel that is removed is the pixel in the center of the tightest cluster.
In the second phase (Phase II) the Initial Binary Pattern is again used as the starting basis and one minority pixel (or "1") is inserted at a time into the Initial Binary Pattern while, in parallel, its rank is entered into the dither array. In each case, the minority pixel that is inserted is done so at the location of a "0" identified as the center of the largest void.
Finally, in Phase III the Initial Binary Pattern produced by adding "1's" in Phase II is used as the starting point. In Phase III, the meaning of "minority pixel" is reversed from "1" to "0" because there are more 1's than 0's in the Initial Binary Pattern due to "1's" being added in Phase II. The Initial Binary Pattern is now filled with more and more 1's while the dither array continues to be filled with the rank values. In each step a "1" is inserted in the "0" location identified in the tightest cluster of minority pixels. At the end of Phase III, the Initial Binary Pattern is filled with all 1's and the dither array is filled with a unique rank value in each element from 0 to the maximum of pixels.
While the void and cluster method produces a dither array that, in turn, generates high-quality halftoned images that are generally artifact-free there is still some tonal distortion and the resulting image can be further improved.
Accordingly, it is an object of the present invention to reduce the tonal distortion produced by halftoning using a dither array generated by the void-and-cluster method.
It is a further object of the present invention to generate an ordered dispersed-dot dither array of arbitrary size wherein the dots are distributed homogeneously.